package bintree.segment_tree;

import java.util.Arrays;
import java.util.NoSuchElementException;

/**
 * @author yuisama
 * @date 2022/12/29 15:55
 * 基于泛型数组的线段树实现(静态区间上的线段树，不考虑区间扩容或删除)
 **/
public class SegmentTree<E> {
    // 数据所在的具体数组
    private Object[] data;
    // 线段树 - 长度为数据的4n(将线段树看做满二叉树，浪费一部分空间)
    private Object[] tree;

    // 初始化，整个区间元素为arr
    public SegmentTree(E[] arr) {
        // 先将整个区间元素内容写入data数组
        data = Arrays.copyOf(arr,arr.length);
        // 线段树初始化空间
        tree = new Object[4 * data.length];
    }

    /**
     * 在线段树中检索某个索引值
     * @param index
     * @return
     */
    public E get(int index) {
        if (!rangeCheck(index)) {
            throw new NoSuchElementException("index illegal!cannot get!");
        }
        return (E) this.data[index];
    }

    /**
     * 当前线段树中节点个数
     * @return
     */
    public int getSize() {
        return data.length;
    }

    private boolean rangeCheck(int index) {
        if (index < 0 || index >= data.length) {
            return false;
        }
        return true;
    }

    // 线段树左子树索引编号，以0开始编号
    private int leftChild(int k) {
        return k << 1 + 1;
    }

    // 线段树右子树编号
    private int rightChild(int k) {
        return k << 1 + 2;
    }
}